package HashBuck;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 故我
 * Date: 2024-02-07
 * Time: 19:54
 */
public class HashDemo {
    static class Node {
        private int key;
        private int value;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] Nodes;//存储节点数组
    private int useSize;
    private static final float Default_Load_Foctor = 0.75f;//默认的负载因子

    public HashDemo() {
        Nodes = new Node[10];//默认数组
    }

    /**
     * 插入元素
     */
    public void put(int key, int value) {
        // 计算下标
        int index = key % Nodes.length;
        // 通过遍历看数组中是否含有该key值，如果有就更新value   没有就采用头插法进行插入
        Node cur = Nodes[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;//单链表向后走
        }
        // 走到这里就是用头插法进行插入节点
        Node node = new Node(key, value);
        node.next = Nodes[index];
        Nodes[index] = node;
        useSize++;

        // 判断是否负载因子达到了默认的值
        if (LoadFoctor() > Default_Load_Foctor) {
            // 进行扩容
            //Nodes = Arrays.copyOf(Nodes, 2 * Nodes.length); //这个扩容 error 所有节点需要重新计算哈希
            Resize();
        }
    }

    private void Resize() {
        Node[] newNodes = new Node[2 * Nodes.length];
        // 重新遍历节点进行新数组的哈希
        for (int i = 0; i < Nodes.length; i++) {
            Node cur = Nodes[i];
            while (cur != null) {
                // 记录一下原来节点的下一个节点
                Node tmp = cur.next;
                int newindex = cur.key % newNodes.length;
                // 头插法插入新的数组中
                cur.next = newNodes[newindex];
                newNodes[newindex] = cur;
                cur = tmp;
            }
        }
        Nodes = newNodes;
    }

    public float LoadFoctor() {
        return useSize * 1.0f / Nodes.length;
    }

    public int get(int key) {
        // 获取 key 的value值
        int index = key % Nodes.length;
        Node cur = Nodes[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;//找不到
    }

}
